package codingInterview.leetcode.editor.cn;

//输入一个字符串，打印出该字符串中字符的所有排列。 
//
// 
//
// 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 
//
// 
//
// 示例: 
//
// 输入：s = "abc"
//输出：["abc","acb","bac","bca","cab","cba"]
// 
//
// 
//
// 限制： 
//
// 1 <= s 的长度 <= 8 
// Related Topics 字符串 回溯 👍 513 👎 0

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

//Java：剑指 Offer 38 - 字符串的排列
public class ZiFuChuanDePaiLieLcof{
    public static void main(String[] args) {
                Solution solution = new ZiFuChuanDePaiLieLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        List<String> res = new ArrayList<>();
        char[] chars;
    public String[] permutation(String s) {
        this.chars = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    private void dfs(int index){
        if(index == chars.length-1){ //固定到了最后一位
            res.add(String.valueOf(chars));
            return;
        }
        HashSet<Character> set = new HashSet<>(); //用于判断重复
        for (int i = index; i < chars.length; i++) {
            if(set.contains(chars[i])) continue;
            set.add(chars[i]);
            swap(index,i); //交换
            dfs(index+1); // 固定第index+1
            swap(i,index); // 恢复交换
        }
    }
    private void swap(int a, int b){
        char tmp = chars[a];
        chars[a] = chars[b];
        chars[b] = tmp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
